//package work.rightAnswer;
//
//import java.util.ArrayList;
//import java.util.HashSet;
//import java.util.List;
//import java.util.Set;
//
//class Solution {
//    public List<String> findWords(char[][] board, String[] words) {
//        //矩阵遍历-dfs + 前缀树
//        //插入words到前缀树中
//        Trie root = new Trie();
//        for (String word : words) {
//            root.insert(word);
//        }
//
//        Set<String> set = new HashSet<>();
//        //遍历双重矩阵
//        for (int i = 0; i < board.length; i++) {
//            for (int j = 0; j < board[0].length; j++) {
//                //判断当前字符为起始元素，能不能在前缀树中找到整个字符
//                char ch = board[i][j];
//                queryForStringByDFS(board,i,j,root,new HashSet<>(),new StringBuilder(),set);
//            }
//        }
//
//        return new ArrayList<>(set);
//
//    }
//
//    private void queryForStringByDFS(char[][] board, int i, int j, Trie root, HashSet<Integer> hashSet, StringBuilder stringBuilder, Set<String> set) {
//        //单次遍历逻辑-中上下左右
//        //中逻辑
//        //1.越界，直接不讨论return
//        if(i<0||i>=board.length||j<0||j>=board[0].length){
//            return;
//        }
//
//
//        //判断是否有子元素，没有就return。通常情况下的讨论，root为父节点，字符为边，根据有无子树判断是否有字符。
//        char ch = board[i][j];
//        if(root.children[ch-'a']==null){
//            return;
//        }
//
//        //如果没访问过，先不管后续如何，先加入到哈希表中
//        if(hashSet.contains(i*board[0].length+j)){
//            return;
//        }
//        hashSet.add(i*board[0].length+j);
//
//        stringBuilder.append(ch);
//        //如何当前子元素存在，且isEnd为true，那么可以断定，这就是结尾节点,直接入set表(可能和重合子字符串，所以继续遍历)
//            if(root.children[ch-'a'].isEnd==true){
//            set.add(stringBuilder.toString());
//        }
//
//
//        queryForStringByDFS(board,i-1,j,root.children[ch-'a'],hashSet,stringBuilder,set);
//        queryForStringByDFS(board,i+1,j,root.children[ch-'a'],hashSet,stringBuilder,set);
//        queryForStringByDFS(board,i,j-1,root.children[ch-'a'],hashSet,stringBuilder,set);
//        queryForStringByDFS(board,i,j+1,root.children[ch-'a'],hashSet,stringBuilder,set);
//
//        stringBuilder.deleteCharAt(stringBuilder.length()-1);
//        hashSet.remove(i*board[0].length+j);
//    }
//
//
//}
//
//
//class Trie{
//    boolean isEnd;
//    Trie[] children;
//
//    public Trie(){
//        children = new Trie[26];
//        isEnd = false;
//    }
//
//    //插入单词word
//    public void insert(String word){
//        Trie node = this;
//        //遍历每个字符
//        for (int i = 0; i < word.length(); i++) {
//            //如果没有孩子节点，那就创建一个
//            char ch = word.charAt(i);
//            if(node.children[ch-'a']==null){
//                node.children[ch-'a'] = new Trie();
//            }
//            node = node.children[ch-'a'];
//        }
//        //遍历完后，设置最后的节点isEnd = true;
//        node.isEnd = true;
//    }
//}